import collections


class Solution:
    def minSetSize(self, arr: list) -> int:
        counter = collections.Counter()
        for num in arr:
            counter[num] += 1
        ans = 0
        length = len(arr)
        for i in sorted(counter.values(), reverse=True):
            length -= i
            ans += 1
            if length <= len(arr) // 2:
                return ans
        return ans
